class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        vector<int> hash(26, -1001);
        for(int i = 0; i < chars.size(); ++i)
        {
            int a = chars[i] - 'a';
            hash[a] = vals[i];
        }

        for(int i = 0; i < 26; ++i)
        {
            if(hash[i] == -1001) hash[i] = i + 1;
            // cout << hash[i] << " ";
        }

        int dp = 0, pre = 0, ret = 0;
        for(int i = 1; i <= s.size(); ++i)
        {
            int cur = hash[s[i - 1] - 'a'];
            dp = max(pre + cur, cur);
            pre = dp;
            ret = max(ret, dp);
        }
        return ret;
    }
};
